package base.Chapter01_Sort;

import utils.CommonUtils;

import java.util.Arrays;

/**
 * 选择排序
 * 1, 分为已排序区A 和 未排序区B
 * 2, 在B中选一个最小的, 放到A的末尾
 */
public class C03_SelectionSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 循环1: 确定A
        for (int i = 0; i < arr.length - 1; i++) {
            // 循环2: 找B中最小, 并交换到A末尾
            // 找最小
            int minElementIndex = findMinElementIndex(arr, i + 1);
            // 交换, 放到A中最后位置
            CommonUtils.swap(arr, i, minElementIndex);
        }
    }

    /**
     * 作用: 在arr数组的指定区间找最小元素的索引
     *
     * @param arr 目标区间
     * @param j   起始点索引
     * @return 最小元素的索引
     */
    public static int findMinElementIndex(int[] arr, int j) {
        int minElementIndex = j;
        for (int i = j + 1; i < arr.length; i++) {
            if (arr[i] <= arr[minElementIndex]) {
                minElementIndex = i;
            }
        }
        return minElementIndex;
    }

    public static void main(String[] args) {
        int[] arr = {19, 100, 50, 4, 1};
        sort(arr);
        Arrays.stream(arr).mapToObj(element -> element + " ").forEach(System.out::printf);
    }
}
